//
//  13-14.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/2/26.
//

import Foundation

class Node: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(userId)
    }
    
    static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs.userId == rhs.userId
    }
    
    /// 结点的名称，这里使用用户id
    var userId: Int
    /// 朋友集合
    var friends: Set<Node>? = nil
    /// 几度好友
    var degree: Int
    /// 用于存放从不同用户出发，到当前用户是第几度结点
    var degrees: [Int: Int] = [Int: Int]()
    
    init(userId: Int) {
        self.userId = userId
        friends = Set<Node>()
        self.degree = 0
        self.degrees[userId] = 0
    }
}

func bfs(userNodes: [Node], userId: Int) {
    if userId >= userNodes.count { return }
    // 用于存放userId的队列
    var queue: Queue<Int> = Queue()
    // 放入初始节点
    queue.enqueue(userId)
    // 存放已经被访问过的结点，防止回路
    var visited = Set<Int>()
    visited.insert(userId)
    
    while !queue.isEmpty {
        // 拿出队列头部的第一个结点
        let currentUserId = queue.dequeue()!
        // 遍历刚刚拿出的这个结点的所有直接连接结点，并加入队列尾部
        for node in userNodes[currentUserId].friends! {
            if visited.contains(node.userId) {
                continue
            }
            queue.enqueue(node.userId)
            visited.insert(node.userId)
            node.degree = userNodes[currentUserId].degree + 1
            print("\t\(node.degree)度好友：\(node.userId)")
        }
    }
}
